/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
int lower_bound(int *nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1;
    
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] >= target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* ans = malloc(sizeof(int) * 2);

    int start = lower_bound(nums, numsSize, target);
    if(start == numsSize || nums[start] != target){
        ans[0] = -1;
        ans[1] = -1;
        return ans;
    }

    int end = lower_bound(nums, numsSize, target + 1) - 1;
    ans[0] = start;
    ans[1] = end;
    return ans;
}


/*给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。*/